백준 1916번

오늘 풀어본 문제는 백준의 1916번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 4

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

$N$ 개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 $M$ 개의 버스가 있다. 우리는 $A$ 번째 도시에서 $B$ 번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. $A$ 번째 도시에서 $B$ 번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 $1$ 부터 $N$ 까지이다.

입력

첫째 줄에 도시의 개수 $N$ $(1 \leq N \leq 1,000)$ 이 주어지고 둘째 줄에는 버스의 개수 $M$ $(1 \leq M \leq 100,000)$ 이 주어진다. 그리고 셋째 줄부터 $M+2$ 줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 $0$ 보다 크거나 같고, $100,000$ 보다 작은 정수이다.

그리고 $M+3$ 째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

풀이과정

1번째 시도

이 문제를 처음 보고 다익스트라 알고리즘을 사용하여 최단 경로를 찾는 문제라는 것을 알 수 있었다. 버스로 이동하는 비용을 각 간선의 길이로 생각하여 그래프를 구성하면 쉽게 풀 수 있는 문제라고 생각했다.

코드는 다음과 같이 작성하였다.

#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;

int N, M;
vector<int> shortest;
vector<pii> graph[1001];

struct cmp {
	bool operator()(const pii& p1, const pii& p2) {
		return p1.second > p2.second;
	}
};

void dijkstra(int departure);

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N;
	shortest.resize(N + 1, INT_MAX);

	cin >> M;

	for (int i = 0; i < M; i++) {
		int start, end, cost;
		cin >> start >> end >> cost;

		graph[start].emplace_back(make_pair(end, cost));
	}

	int departure, destination;
	cin >> departure >> destination;

	dijkstra(departure);

	cout << shortest[destination];

	return 0;
}

void dijkstra(int departure) {
	priority_queue<pii, vector<pii>, cmp> pq;

	shortest[departure] = 0;
	pq.push(make_pair(departure, 0));

	while (!pq.empty()) {
		pii currentNode = pq.top();
		pq.pop();

		for (auto& nextNode : graph[currentNode.first]) {
			if (shortest[nextNode.first] > shortest[currentNode.first] + nextNode.second) {
				shortest[nextNode.first] = currentNode.second + nextNode.second;
				pq.push(make_pair(nextNode.first, shortest[nextNode.first]));
			}
		}
	}
}

실행 결과 ‘시간 초과’ 가 발생하였다.

2번째 시도

분명 다익스트라 알고리즘을 제대로 구현했다고 생각했는데 시간 초과가 나와서 당황했다. 비슷한 상황을 겪은 사람이 있을까 해서 질문 게시판을 확인해보았고, 무엇이 문제인지 알 수 있었다.

우선순위 큐에서 이미 더 짧은 길이의 경로로 업데이트된 정점이 더 비효율적인 경로의 길이를 가지고 다른 노드의 거리를 업데이트 하는 절차를 거치는 것이 문제였다. 길이가 당연히 더 길기 때문에 진짜로 업데이트가 이루어지는 것은 아니지만, 비교하는 작업을 거치는 과정 자체가 불필요하게 수행되었던 것이다.

코드는 다음과 같이 수정하였다.

#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;

int N, M;
vector<int> shortest;
vector<pii> graph[1001];

struct cmp {
	bool operator()(const pii& p1, const pii& p2) {
		return p1.second > p2.second;
	}
};

void dijkstra(int departure);

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> N;
	shortest.resize(N + 1, INT_MAX);

	cin >> M;

	for (int i = 0; i < M; i++) {
		int start, end, cost;
		cin >> start >> end >> cost;

		graph[start].emplace_back(make_pair(end, cost));
	}

	int departure, destination;
	cin >> departure >> destination;

	dijkstra(departure);

	cout << shortest[destination];

	return 0;
}

void dijkstra(int departure) {
	priority_queue<pii, vector<pii>, cmp> pq;

	shortest[departure] = 0;
	pq.push(make_pair(departure, 0));

	while (!pq.empty()) {
		pii currentNode = pq.top();
		pq.pop();

		if (currentNode.second > shortest[currentNode.first]) continue;

		for (auto& nextNode : graph[currentNode.first]) {
			if (shortest[nextNode.first] > shortest[currentNode.first] + nextNode.second) {
				shortest[nextNode.first] = currentNode.second + nextNode.second;
				pq.push(make_pair(nextNode.first, shortest[nextNode.first]));
			}
		}
	}
}

그러자 모든 테스트 케이스를 통과하고 정답이 나오는 것을 확인할 수 있었다.

마무리

처음에 문제를 보고 간단한 다익스트라 알고리즘 문제라고 좋아했는데, 뒤통수를 맞아버렸다. ‘틀렸습니다’가 나올 수는 있겠다고 생각했지만 ‘시간 초과’는 전혀 예상하지 못했다. 당황스럽긴 했어도 앞으로 다익스트라 알고리즘을 쓸 때 어떻게 최적화를 할 수 있는지를 배울 수 있었던 꽤 유익했던 문제였다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/1916

← Previous Post Next Post →